home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / missionaries / mandc.sml < prev    next >
Encoding:
Text File  |  1995-12-30  |  1.8 KB  |  56 lines  |  [TEXT/R*ch]
  1. (* Missionaries and canabals state space *)
  2. structure MandC =
  3. struct
  4.  
  5.   datatype loc = LEFT | RIGHT  (* location of boat *)
  6.  
  7.   type sit = {mis:int,can:int,boat:loc}
  8.   type state = sit list
  9.  
  10.   (* sit, short for situation, represents number of missionaries and canabals
  11.        where the boat is, and the location of the boat.
  12.      state is a list of situation, representing a history of moves *)
  13.  
  14.   fun member(s, []:state) = false
  15.     | member(s,s'::rest) = s = s' orelse member(s,rest)
  16.  
  17.   (* safe checks that there are at least as many missionaries as canabals
  18.      where ever they are mixed, and also checks that the latest situation
  19.      hasn't occurred before in the state *)
  20.   fun safe((new as {mis,can,...})::old : state) = 
  21.       (mis=0 orelse (mis>=can andalso (3-mis = 0 orelse 3-mis >= 3-can)))
  22.       andalso not(member(new,old))
  23.  
  24.   fun printSit (h:string) ({mis,can,boat}: sit) =
  25.         (print h; print mis;
  26.          print " "; print can;
  27.          print " "; case boat of LEFT => print "LEFT" | _ => print "RIGHT";
  28.      print "\n")
  29.  
  30.   fun goal(s as {mis=3,can=3,boat=RIGHT}::_ : state) = 
  31.         (app (fn sit => printSit "% " sit) (rev s); true)
  32.     | goal(sit::_) =
  33.     (printSit "? " sit; false)
  34.  
  35.   (* possible configurations of passengers on the canoe, (missionaries,canabals) *)
  36.   val passengers = [(2,0),(1,1),(0,2),(1,0),(0,1)]
  37.  
  38.   fun cross LEFT = RIGHT
  39.     | cross RIGHT = LEFT
  40.  
  41.   (* moves generates list of possible successors of its state argument *)
  42.   fun moves (s as {mis,can,boat}::_) = 
  43.       let fun mv [] = []
  44.         | mv ((m,c)::rest) =
  45.         if mis >= m andalso can >= c 
  46.         then ({mis=3-mis+m,can=3-can+c,boat=cross(boat)}::s)::mv rest
  47.         else mv rest
  48.        in fold (fn (s,l) => if safe s then s::l else l) (mv passengers) []
  49.       end
  50.  
  51.   val initial : state = [{mis=3, can=3, boat=LEFT}]  (* initial state *)
  52.  
  53. end (* MandC *)
  54.  
  55.  
  56.